# 最高有效位

def countBits(n):
    bits = [0]
    high_bit = 0
    for i in range(1, n + 1):
        if i & (i - 1) == 0:  # 此时 i 为 2 的 次方数
            high_bit = i
        bits.append(bits[i - high_bit] + 1)
    return bits


print(countBits(2))  # [0,0,1]
print(countBits(5))  # [0,1,1,2,1,2]
